package com.myString;

/**
 * @Author: linKe
 * @Date: 2022/1/2 1:31
 * @FileName: MyString1
 * @version: 1.0
 * @Description: 自定义字符串实现类
 */
public class MyStringAchieve implements MyString {
    /**
     * 字符数组
     */
    char[] element;
    /**
     * kmp算法 数字数组
     */
    static  int[] next;
    /**对象个数（长度）*/
    int n;

    public MyStringAchieve(){
        this(64);
    }
    /**构造容量为length的空表）*/
    public MyStringAchieve(int length){
        //申请数组的存储空间，元素为null
        this.element= new char[length];
        this.n=0;
    }
    /**构造容量为length的空表）*/
    public MyStringAchieve(int length,char[] chars,int n){
        //申请数组的存储空间，元素为null
        this.element= new char[length];
        this.n=n;
        this.element = chars;
    }
    /**
     * 返回字符元素的长度
     * @return  结果
     */
    @Override
    public int length() {
        return this.n;
    }

    @Override
    public char charAt(int i) {

        if(i>=0 && i<this.n) {
            //返回数组元素引用的对象，传递对象引用
            return this.element[i];
        }
        return '-';
    }

    @Override
    public void setCharAt(int i, char ch) {
        if(i>=0 && i<this.n) {
            element[i] = ch;
        }
    }

    @Override
    public MyString subString(int begin, int end) {
        MyString myString = new MyStringAchieve();
        //记录子串的数据长度
        int count=0;
        //记录子串的数据值
        char[] temp=new char[this.element.length];
        for (int i = begin; i < end; i++) {
            temp[count]=this.element[i];
            count ++;
        }

        return new MyStringAchieve(count,temp,count);
    }

    @Override
    public MyString concat(MyString ms) {
        return null;
    }

    @Override
    public MyString insert(int i, MyString ms) {
        return null;
    }

    @Override
    public MyString delete(int begin, int end) {
        return null;
    }

    /**
     * BF算法描述和实现
     * 返回当前串（目标串）中首歌与模式串pattern匹配的子串序号，
     * 匹配失败时返回-1
     * @param pattern   匹配的字符串
     * @return  结果
     */
    @Override
    public int indexOf(MyString pattern) {
      return this.indexOf(pattern,0);
    }

    /**
     * BF算法描述和实现    增加匹配开始下标的设置
     * @param pattern   匹配的字符串
     * @param begin   匹配的字符串开始下标
     * @return  结果
     */
    public int indexOf(MyString pattern,int begin) {
        int n = this.length(),m = pattern.length();
        if (begin<0){
            begin=0;
        }
        //若目标为空，较短或begin越界 直接返回下标越界-1
        if (n==0||n<m||begin>n){
            return -1;
        }
        //i,j 分别为目标传和模式串当前下标
        int i=begin,j=0;
        //记载比较次数
        int count=0;
        while(i<n&&j<m){
            count++;
            //若当前两字符相等，则继续比较后续字符
            if (this.charAt(i)== pattern.charAt(j)){
                i++;
                j++;
            }else{
                //否则i,j回溯，进行下次匹配
                //目标串下标i，退回到下个匹配字符子串序号
                i = i - j + 1;
                //模式串下标j，退回到0
                j=0;
                //若目标串剩余子串的长度<m，不再比较
                if (i>n-m){
                    break;
                }
            }
        }
        System.out.println("BF.count="+count);
        //匹配成功
        if (j==m){
            //返回匹配的子串序号
            return i-j;
        }
        //匹配失败时返回-1
            return -1;
    }

    /**
     * BF算法描述和实现    增加匹配开始下标的设置
     * @param pattern   匹配的字符串
     * @param begin   匹配的字符串开始下标
     * @return  结果
     */
    public int indexOf(String target,String pattern,int begin) {
        int n=target.length(), m=pattern.length();
        //对begin容错，若begin<0，从0开始
        if (begin<0)
        {
            begin = 0;
        }
        //若目标串空、较短或begin越界，不需比较
        if (n==0 || n<m || begin>=n)
        {
            return -1;
        }
        //返回模式串pattern的next数组
        next = getNext(pattern);
        //i、j分别为目标串、模式串比较字符下标
        int i=begin, j=0;
        while (i<n && j<m)
        {
            if (j==-1 || target.charAt(i)==pattern.charAt(j))
            //若当前两字符相等，则继续比较后续字符
            {
                i++;
                j++;
            }
            //否则，下次匹配，目标串下标i不回溯
            else
            {//模式串下标j退回到下次比较字符序号
                j=next[j];
                //若目标串剩余子串的长度不够，不再比较
                if (n-i+1<m-j+1)
                {
                    break;
                }
            }
        }
        //匹配成功
        if (j==m)
        //返回匹配的子串序号
        {
            return i-j;
        }
        //匹配失败
        return -1;

    }

    private static int[] getNext(String pattern) //返回模式串pattern的next数组
    {
        int j=0, k=-1;
        next=new int[pattern.length()];
        next[0]=-1;
        while (j<pattern.length()-1) {
            if (k==-1 || pattern.charAt(j)==pattern.charAt(k))
            {
                j++;
                k++;
                next[j]=k;
            }
            else {
                k=next[k];
            }
        }
        return next;
    }
    @Override
    public void removeAll(MyString pattern) {

    }

    @Override
    public void replaceAll(MyString pattern, MyString ms) {

    }
}
